|
In graph theory, a bound graph expresses which pairs of elements of some partially ordered set have an upper bound. Rigorously, any graph ''G'' is a bound graph if there exists a partial order ≤ on the vertices of ''G'' with the property that for any vertices ''u'' and ''v'' of ''G'', ''uv'' is an edge of ''G'' if and only if ''u'' ≠ ''v'' and there is a vertex ''w'' such that ''u'' ≤ ''w'' and ''v'' ≤ ''w''. Bound graphs are sometimes referred to as ''upper bound graphs'', but the analogously defined lower bound graphs comprise exactly the same class—any lower bound for ≤ is easily seen to be an upper bound for the dual partial order ≥. == References == * * * * 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Bound graph」の詳細全文を読む スポンサード リンク
|